package newcoder_exp.justPractise;
import java.util.*;

import org.junit.*;
//哈夫曼编码
public class Pra9 {
    
    class Node<T> implements Comparable<Node<T>> {
        T val;//存放的节点数据
        Node<T> left, right;//左右孩子
        int times; //频次
        String code; //当前节点的编码，包含非叶子节点

        public Node(T val, int times) {
            this.val = val;
            this.times = times;
            this.code = "";
        }
        public Node(int times) {
            this.times = times;
            this.code = "";
        }

        @Override
        public int compareTo(Node<T> o) {
            return this.times - o.times;
        }    
}

    public Node<Character> createTree(List<Node<Character>> nodes) {
        //小顶堆，频次最小的存放在堆顶
        Queue<Node<Character>> queue = new PriorityQueue<>();
        queue.addAll(nodes);
        Node<Character> left, right, p = null;
        while(queue.size() > 1) {
            left = queue.poll();
            right = queue.poll();
            p = new Node<Character>(left.times + right.times);
            p.left = left;
            p.right = right;
            queue.offer(p);
        }
        return p;
    }

    public List<Node<Character>> getTimes(char[] cs) {
        int[] dict = new int[26];
        for (int i = 0; i < cs.length; i++) {
            dict[cs[i] - 'a']++;
        }
        List<Node<Character>> res = new ArrayList<>();
        Node<Character> cur = null;
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < 26; i++) {
            if (dict[i] != 0) {
                cur = new Node<>((char)(i + 'a'), dict[i]);
                res.add(cur);
                map.put((char)(i + 'a'), dict[i]);
            }
        }
        System.out.println(map);
        return res;
    }

    //通过层序遍历给每个位置进行编码
    public Map<Character, String> huffmanDecode(Node<Character> head) {
        Queue<Node<Character>> queue = new LinkedList<>();
        queue.offer(head);
        int n;
        Node<Character> cur, left, right;
        Map<Character, String> res = new HashMap<>();
        while (!queue.isEmpty()) {
            n = queue.size();
            for (int i = 0; i < n; i++) {
                cur = queue.poll();
                left = cur.left;
                right = cur.right;
                if (left == null && right == null) {
                    //叶子节点，记录编码
                    res.put(cur.val, cur.code);
                    continue;
                }
                //给左孩子编码0，右孩子编码1
                if (left != null) {
                    left.code = cur.code + "0";
                    queue.offer(left);
                }
                if (right != null) {
                    right.code = cur.code + "1";
                    queue.offer(right);
                }
            }
        }
        return res;
    } 

    public Map<Character, String> huffman(String s) {
        Node<Character> head = createTree(getTimes(s.toCharArray()));
        return huffmanDecode(head);
    }

    @Test
    public void test() {
        String s = "abbcccddddeeeeeffffff";
        // Node<Character> head = createTree(getTimes(s.toCharArray()));
        // System.out.println(huffmanDecode(head));;
        System.out.println(huffman(s));
    }
}
